//给你一个二进制字符串 s 和一个正整数 k 。 
//
// 如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个 美丽子字符串 。 
//
// 令 len 等于 最短 美丽子字符串的长度。 
//
// 返回长度等于 len 且字典序 最小 的美丽子字符串。如果 s 中不含美丽子字符串，则返回一个 空 字符串。 
//
// 对于相同长度的两个字符串 a 和 b ，如果在 a 和 b 出现不同的第一个位置上，a 中该位置上的字符严格大于 b 中的对应字符，则认为字符串 a 字典
//序 大于 字符串 b 。 
//
// 
// 例如，"abcd" 的字典序大于 "abcc" ，因为两个字符串出现不同的第一个位置对应第四个字符，而 d 大于 c 。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "100011001", k = 3
//输出："11001"
//解释：示例中共有 7 个美丽子字符串：
//1. 子字符串 "100011001" 。
//2. 子字符串 "100011001" 。
//3. 子字符串 "100011001" 。
//4. 子字符串 "100011001" 。
//5. 子字符串 "100011001" 。
//6. 子字符串 "100011001" 。
//7. 子字符串 "100011001" 。
//最短美丽子字符串的长度是 5 。
//长度为 5 且字典序最小的美丽子字符串是子字符串 "11001" 。
// 
//
// 示例 2： 
//
// 
//输入：s = "1011", k = 2
//输出："11"
//解释：示例中共有 3 个美丽子字符串：
//1. 子字符串 "1011" 。
//2. 子字符串 "1011" 。
//3. 子字符串 "1011" 。
//最短美丽子字符串的长度是 2 。
//长度为 2 且字典序最小的美丽子字符串是子字符串 "11" 。 
// 
//
// 示例 3： 
//
// 
//输入：s = "000", k = 1
//输出：""
//解释：示例中不存在美丽子字符串。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 100 
// 1 <= k <= s.length 
// 
//
// Related Topics 字符串 滑动窗口 👍 13 👎 0

package leetcode.editor.cn;
//java:最短且字典序最小的美丽子字符串
public class Q2904ShortestAndLexicographicallySmallestBeautifulString {
    public static void main(String[] args){
        Solution solution = new Q2904ShortestAndLexicographicallySmallestBeautifulString().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        //        String res = "";
//        int len = s.length(), left = 0, countOne = 0;
//
//        // 判定是否能够满足题意
//        for (int i = 0; i < len; i++) {
//            res += s.charAt(i);
//            if (s.charAt(i) == '1') {
//                countOne++;
//            }
//        }
//        if (countOne < k) {
//            return "";
//        }
//
//        // 滑动窗口解决问题
//        res = s;
//        countOne = 0;
//        // 扩大右边界
//        for (int right = 0; right < len; right++) {
//            if (s.charAt(right) == '1') {
//                countOne++;
//            }
//            // 缩小左边界，遇到0也要继续缩小
//            while (countOne > k || s.charAt(left) == '0') {
//                if (s.charAt(left) == '1') {
//                    countOne--;
//                }
//                left++;
//            }
//            // 找到满足题意的时候比较字符串
//            if (countOne == k) {
//                res = minString(res, s.substring(left, right + 1));
//            }
//        }
//        return res;

        // 判定整个字符串是否满足题意的简单写法
        if (s.replace("0", "").length() < k) {
            return "";
        }
        char[] chars = s.toCharArray();
        int len = s.length(), left = 0, countOne = 0;
        String res = s;
        for (int right = 0; right < len; right++) {
            countOne += chars[right] - '0';
            while (countOne > k || chars[left] == '0') {
                countOne -= chars[left] - '0';
                left++;
            }
            if (countOne == k && compare(s.substring(left, right + 1), res)) {
                res = s.substring(left, right + 1);
            }
        }
        return res;
    }

    // 判定s是否字典序小于t
    public boolean compare(String s, String t) {
        return s.length() < t.length() || (s.length() == t.length() && s.compareTo(t) < 0);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}